package com.wdc.queue;

import java.util.Arrays;

/**
 * 基于无序数组实现
 */
public class TestPriorityQueue1 <E extends  Priority > implements Queue<E> {
    public static void main(String[] args) {
        TestPriorityQueue1<Entry> queue = new TestPriorityQueue1<Entry>(5);
        queue.offer(new Entry("tssk1",4));
        queue.offer(new Entry("tssk2",3));
        queue.offer(new Entry("tssk3",2));
        queue.offer(new Entry("tssk4",1));
        queue.offer(new Entry("tssk5",5));

        System.out.println(queue.peek());
        System.out.println(queue.peek());
    }

    Priority[] array;
    int size;

    public TestPriorityQueue1(int capacity) {
        array = new Priority[capacity];

    }

    @Override
    public boolean offer(E value) {
        if (isFull()){
            return false;
        }
        array[size++] = value;


        return true;
    }


    /**
     * 返回优先级最高的索引
     * @return
     */
    private int selectMax(){
        int maxIndex = 0;
        for (int i = 1; i < size; i++) {
            if (array[i].priority() > array[maxIndex].priority()){
                maxIndex = i;
            }
        }
        return maxIndex;


    }


    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int max = selectMax();
        return (E) array[max];
    }

    @Override

    public E peek() {

        if (isEmpty()) {
            return null;
        }
        int max = selectMax();
        E removed = (E) array[max];
        remove(max);

        return removed;
    }

    private void remove(int index) {
        if (index < size -1){
            //移动
            System.arraycopy(array,index + 1,array,index,size - 1 -index );

        }
        size--;

        array[--size] = null;  //help GC
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}

